package _stack_queue

import org.junit.Assert
import org.junit.Test
import java.util.*

/**
 * https://www.bilibili.com/video/BV1kd4y1o7on/?vd_source=f6c1b6be6f0ddb81b8fd2663a74a3efb
 * https://leetcode.cn/problems/evaluate-reverse-polish-notation/description/
 *
 * 150. 逆波兰表达式求值
 *
 * 示例 1：
 *
 * 输入：tokens = ["2","1","+","3","*"]
 * 输出：9
 * 解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
 * 示例 2：
 *
 * 输入：tokens = ["4","13","5","/","+"]
 * 输出：6
 * 解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
 * 示例 3：
 *
 * 输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
 * 输出：22
 * 解释：该算式转化为常见的中缀算术表达式为：
 *   ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
 * = ((10 * (6 / (12 * -11))) + 17) + 5
 * = ((10 * (6 / -132)) + 17) + 5
 * = ((10 * 0) + 17) + 5
 * = (0 + 17) + 5
 * = 17 + 5
 * = 22
 *
 */
class leetcode_150 {
    @Test
    fun test_1() {
        Assert.assertEquals(9, evalRPN(arrayOf("2", "1", "+", "3", "*")))
    }

    @Test
    fun test_2() {
        Assert.assertEquals(6, evalRPN(arrayOf("4", "13", "5", "/", "+")))
    }

    @Test
    fun test_3() {
        Assert.assertEquals(22, evalRPN(arrayOf("10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+")))
    }

    fun evalRPN(tokens: Array<String>): Int {
        // 逆波兰表达式相当于是二叉树中的后序遍历
        // 后缀表达式
        /**
        stack
        loop aray{
        if(符号){
        n1 = pop
        n2 = pop
        stack.push(n1 运算 n2)
        }
        else{
        stack.push
        }
        }
        return stack.pop

         */

        val stack: LinkedList<String> = LinkedList<String>()
        for (str in tokens) {
            if (str == "+" || str == "-" || str == "*" || str == "/") {
                val r: Int = op(stack, str)
                stack.push("" + r)
            } else {
                stack.push(str)
            }
        }
        val r: String = stack.pop()
        return r.toInt()
    }

    private fun op(stack: LinkedList<String>, str: String): Int {
        val n2: Int = stack.pop().toInt()
        val n1: Int = stack.pop().toInt()
        if (str == "+") {
            return n1 + n2
        } else if (str == "-") {
            return n1 - n2
        } else if (str == "*") {
            return n1 * n2
        } else {
            return n1 / n2
        }
    }
}